package 常见算法.双指针;

/**
 * @Date 2024/6/24 19:52
 * @description: 复写0
 * .            https://leetcode.cn/problems/duplicate-zeros/
 * @Author LittleNight
 */
public class likou1089 {

    // 注意: 加了限制 就地 的条件之后,这个题并不简单
    public void duplicateZeros2(int[] arr) {
        // 就地 的意思: 不能额外开辟数组 , 暴力枚举会超出时间限制的
        // 法一: 暴力枚举
        int start = 0;
        while(start < arr.length) {
            if(arr[start] != 0) {
                start++;
            }else {
                // 后面再写一个 0
                if(start + 1 < arr.length) {
                    // 从左往右会覆盖掉之前的元素, 那么走下去后面的都是错误的
                    // 从右往左覆盖是没事的
                    int tmp = arr[start + 1];
                    arr[start + 1] = 0;
                    start += 2;
                }
            }
        }
    }
    //----------------------------------------------------
    // 利用双指针, 从后向前完成复习(都是模拟的过程)
    // 时间: 虽然是两个 while 循环,但是是 N + N 也就是 O(N)
    // 空间的复杂度: 有限的三个变量,所以是 O(1)

    // 类似于这种题一定要画图模拟一下
    public void duplicateZeros(int[] arr) {
        int cur = 0, dest = -1, len = arr.length;
        // 1.先找到最后一个复写的数
        // 解释一下 dest = -1; 如果是从 0 开始的话就要对首元素有两种情况讨论,做出的反应就是和后面两种情况的逻辑不一致了(不好做出来),所以为了保持一致,引入类似于 头结点的东西

        while(cur < len) {
            if(arr[cur] != 0) {
                dest += 1;
            }else {
                dest += 2;
            }
            // 注意这个判断是在 dest 移动之后才判断的,如果是放在最前面判断,则 cur 的位置会出现在最后一个复写的数的后一个,假如只有一个数,那么就会越界
            // cur 移动之前需要先判断一下 dest 的位置, 来判断是不是要结束了
            if(dest >= len - 1) {  // n - 1 是最后一个位置的下标
                break;
            }
            cur++;
        }
        // 2.判断一下特例, cur == 0 的时候, dest 会跑到数组最后一个元素的后面
        if(dest == len) {
            arr[dest - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 3.从后往前模拟复写操作
        while(cur >= 0) {
            if(arr[cur] == 0) {
                arr[dest] = 0;
                dest--;
                // 两步操作
                arr[dest--] = 0;
                // 注意还有 cur 要往前走
                cur--;
            }else {
                // 不是 0 , 把 cur 的值抄到 dest 位置上就行
                arr[dest--] = arr[cur--];
            }
        }
    }

}
